class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int len = nums.length ;
        int sum =  0;
        for(int x : nums) sum += x ;
        if(sum+target<0 || (sum+target)%2==1) return 0 ;
        sum = (sum+target)/2 ;

        int[][] dp = new int[len+1][sum+1] ;
        dp[0][0] = 1 ;
        for(int i=1 ; i<= len ; i ++){
            for(int j=0 ; j <= sum ; j ++){
                dp[i][j] = dp[i-1][j] ;
                if(j >= nums[i-1]){
                    dp[i][j] += dp[i-1][j-nums[i-1]] ;
                }
            }
        }
        return dp[len][sum] ;
    }
}
